#include <stdio.h>


struct ListNode {
        int val;
         struct ListNode *next;
    };
//反转链表
struct ListNode* reverseList(struct ListNode* head) 
{
    if(head==0||head->next==0)
    {
        return head;
    }
    struct ListNode* n1=NULL;
    struct ListNode* n2=head;
    struct ListNode* n3=head->next;

    while(n2)
    {
        n2->next=n1;

        n1=n2;
        n2=n3;
        if(n3)  
            n3=n3->next;
    }
    
    return n1;
}
//

//移除链表元素
struct ListNode* removeElements(struct ListNode* head, int val) 
{

while(head!=NULL&&head->val==val)
{
    head=head->next;
}
if(head==NULL)
    return NULL;
struct ListNode* cur=head;
struct ListNode* next=cur->next;
while(next)
{
    if(next->val==val)
    {
        cur->next=next->next;
        next=cur->next;
    }
    else
    {
        cur=cur->next;
        next=cur->next;
    }
}
return head;
}


//链表的中间结点
struct ListNode* middleNode(struct ListNode* head) {
    if(head==NULL&&head->next==NULL)
    {
        return head;
    }
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
    
}

//找出单向链表中倒数第 k 个节点。返回该节点的值
int kthToLast(struct ListNode* head, int k) {
    struct ListNode* slow=head;
   struct ListNode* fast=head;
   while(k--)
   {
       fast=fast->next;
   }
   while(fast)
   {
       fast=fast->next;
       slow=slow->next;
   }

   return slow->val;
}

//将两个升序链表合并为一个新的 升序 链表并返回
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if(list1==NULL)
    {
        return list2;
    }
    if(list2==NULL)
    {
        return list1;
    }

    struct ListNode* head=NULL;
    struct ListNode* tail=NULL;
    tail=head=(struct ListNode*)malloc(sizeof(struct ListNode));
    //if(list1->val<list2->val)
    //{
        //head=tail=list1;
        //list1=list1->next;
    //}
    //else
    //{
        //head=tail=list2;
       //list2=list2->next;
   //}
    
    while(list1&&list2)
    {
        if(list1->val<list2->val)
        {
            tail->next=list1;
            list1=list1->next;
           
        }
        else
        {
            tail->next=list2;
            list2=list2->next;
            
        }
        tail=tail->next;
    }
    if(list1)
    {
        tail->next=list1;
    }
    else
    {
        tail->next=list2;
    }
struct ListNode* realhead =head->next;
return realhead;
}



//链表分割

    // ListNode* partition(ListNode* pHead, int x) 
    // {
    //     if(pHead==NULL||pHead->next==NULL)
    //         return pHead; 
    //     ListNode* lesshead =(ListNode*)malloc(sizeof(ListNode));
    //     ListNode* lesstail=lesshead;
    //     ListNode* greaterhead =(ListNode*)malloc(sizeof(ListNode));
    //     ListNode* greatertail=greaterhead;
    //     while (pHead)
    //     {
    //         if(pHead->val<x)
    //         {
    //             lesstail->next=pHead;
    //             lesstail=lesstail->next;
    //         }
    //         else 
    //         {
    //             greatertail->next=pHead;
    //             greatertail=greatertail->next;
    //         }
    //         pHead=pHead->next;
    //     }
    //     greatertail->next=NULL;
    //     lesstail->next=greaterhead->next;
    //     ListNode* newhead =lesshead->next;
    //     return newhead;
    // }

//相交链表
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *curA=headA;
    int Ai=0;
    while(curA)
    {
        Ai++;
        curA=curA->next;
    }
    struct ListNode *curB=headB;
    int Bi=0;
    while(curB)
    {
        Bi++;
        curB=curB->next;
    }
    struct ListNode * longLN=headA;
    struct ListNode * shortLN=headB;
    if(Ai<Bi)
    {
    longLN=headB;
    shortLN=headA;
    }

    int gap=abs(Ai-Bi);
    while(gap--)
    {
        longLN=longLN->next;
    }
    while(longLN)
    {
        if(longLN==shortLN)
        {
            return longLN;
        }
        else
        {
            shortLN=shortLN->next;
            longLN=longLN->next;
        }
    }
    return NULL;

}

//环形链表
bool hasCycle(struct ListNode *head) 
{
 if(head==NULL||head->next==NULL)
 {
    return false;
 }
 struct ListNode *slow=head;
 struct ListNode *fast=head;
 while(fast&&fast->next)
 {
    slow=slow->next;
    fast=fast->next->next;
    if(fast==slow)
    {
        return true;
    }
 }
return false;
}

//环形链表2
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *linkhead=head;
    if(head==NULL||head->next==NULL)
    return NULL;
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
            break;
    }
    if (fast == NULL || fast->next == NULL)
        return NULL;
    while(linkhead)
    {
        if(linkhead==fast)
            break;
        linkhead=linkhead->next;
        fast=fast->next;
    }
return linkhead;
}

//复制复杂链表


struct Node* copyRandomList(struct Node* head) 
{
    if(head==NULL)
    {
        return NULL;
    }
    struct Node* cur=head;
    //插入
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->random=NULL;
        copy->next=NULL;
        copy->val=cur->val;

        copy->next=cur->next;
        cur->next=copy;

        cur=cur->next->next;
    }
    cur=head;
    //复制
    while(cur)
    {
        struct Node* copy=cur->next;
        if(cur->random)
            copy->random=cur->random->next;
        else
            copy->random=NULL;

        cur=cur->next->next;
    }
    //分离
    cur=head;
    struct Node* copyhead=cur->next;
    while(cur)
    {
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
         cur->next=next;
        if(next)
        {
            copy->next=next->next;
        }
        else
        {
            copy->next=NULL;
        }
        cur=next;

    }
	return copyhead;
}

//对链表进行插入排序
struct ListNode* insertionSortList(struct ListNode* head) 
{
    if(head==NULL||head->next==NULL)
        return head;
    struct ListNode* sorthead=head;
    struct ListNode* cur=head->next;
    sorthead->next=NULL;
    while(cur)
    {
        struct ListNode* next=cur->next;
        //头插
        if(cur->val<=sorthead->val)
        {
            cur->next=sorthead;
            sorthead=cur;
        }
        else
        {
            struct ListNode* sortcur=sorthead;
            struct ListNode* sortnext=sortcur->next;
            //中间插入
            while(sortnext)
            {
                if(cur->val<=sortnext->val)
                {
                    sortcur->next=cur;
                    cur->next=sortnext;
                    break;
                }
                else
                {
                    sortcur=sortnext;
                    sortnext=sortnext->next;
                }
            }
            //尾插
            if(sortnext==NULL)
            {
                sortcur->next=cur;
                cur->next=NULL;
            }


        }
        cur=next;
    } 
    return sorthead;   
}

//删除链表中的重复元素-2
struct ListNode* deleteDuplicates(struct ListNode* head ) 
{
    if(head==NULL||head->next==NULL)
        return head;
    struct ListNode* prev=NULL;
    struct ListNode* cur=head;
    struct ListNode* next=cur->next;
    while(next)
    {
        if(cur->val!=next->val)
        {
            prev=cur;
            cur=next;
            next=next->next;
        }
        else 
        {
            while(next&&next->val==cur->val)
            {
                next=next->next;
            }
            if(prev)
            {
                prev->next=next;
            }
            else
            {
                head=next;
            }
            while(cur!=next)
            {
                struct ListNode* tmp=cur;
                cur=cur->next;
                free(tmp);
            }
            if(cur) 
                next=cur->next;
            else
                next=NULL;

        }
        
    }
    return head;
}

